package BinaryTree.前序;


/**
 * 技巧：
 *      迭代 f/w
 *      递归
 *      -> 都 可用 汉译+题感
 *
 * LBLD
 *      二叉树题：
 *          每个 cur 干什么 + 前/后
 *
 * 本题：
 *      LBLD -> 只 curL.n = curR
 *      我的复杂了 cur.left cur.right
 *
 *      curLeft curRight curRes 好用
 */
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node next;
};
public class 填充每个节点的下一个右侧节点指针116 {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }

        // root 单独处理
        if(root.left != null){
            root.left.next = root.right;
        }
        pre(root.left, root.right);
        return root;
    }

    private void pre(Node curLeft, Node curRight) {

        // 左
        if(curLeft != null && curLeft.left != null){
            curLeft.left.next = curLeft.right;
        }
        // 右
        if(curRight != null && curLeft.right != null){
            curRight.left.next = curRight.right;
        }
        // 相隔
        if(curLeft != null && curLeft.right != null && curRight != null && curLeft.left != null){
            curLeft.right.next = curRight.left;
        }

        // 迭代 -> 每个curL+R 独立不干扰 -> 顺序任意
        // if -> 完全题感出的
        if(curLeft != null){
            pre(curLeft.left, curLeft.right);
        }
        if(curRight != null){
            pre(curRight.left, curRight.right);
        }
        if(curLeft != null && curRight != null){
            // 这个 不看答案 根本想不到
            pre(curLeft.right, curRight.left);
        }

        // 有 if curL curR -> 不用 if N r 了
        return;
    }
}


